package tree

// https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
// 锯齿遍历
// 算法: 双向队列 + 依层遍历
// 时间复杂度: O(n)
func ZigzagLevelOrder(root *TreeNode) [][]int {
	retArr := make([][]int, 0)
	if nil == root {
		return retArr
	}
	
	currentNodeArr := make([]*TreeNode, 0)
	currentNodeArr = append(currentNodeArr, root)
	order := 1
	for {
		isAllNil := true
		currentNumArr := make([]int, 0)
		tempNodeArr := make([]*TreeNode, 0)
		for len(currentNodeArr) > 0 {
			currentNode := currentNodeArr[0]
			currentNodeArr = currentNodeArr[1:]
			if nil == currentNode {
				continue
			}
			isAllNil = false
			if order == 1 {
				tempNodeArr = append([]*TreeNode{currentNode.Left}, tempNodeArr...)
				tempNodeArr = append([]*TreeNode{currentNode.Right}, tempNodeArr...)
			} else {
				tempNodeArr = append([]*TreeNode{currentNode.Right}, tempNodeArr...)
				tempNodeArr = append([]*TreeNode{currentNode.Left}, tempNodeArr...)
			}
			currentNumArr = append(currentNumArr, currentNode.Val)
		}
		currentNodeArr = tempNodeArr
		if isAllNil {
			break
		}
		retArr = append(retArr, currentNumArr)
		order = 1 - order
	}
	return retArr
}